<html>
<head><meta charset="utf-8"><title>Design question: identity in syntax trees · t-compiler/rust-analyzer · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/index.html">t-compiler/rust-analyzer</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html">Design question: identity in syntax trees</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="188107098"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188107098" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188107098">(Feb 13 2020 at 13:47)</a>:</h4>
<p>Discussion for <a href="https://github.com/rust-analyzer/rust-analyzer/issues/3129" target="_blank" title="https://github.com/rust-analyzer/rust-analyzer/issues/3129">https://github.com/rust-analyzer/rust-analyzer/issues/3129</a></p>



<a name="188107220"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188107220" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188107220">(Feb 13 2020 at 13:48)</a>:</h4>
<p>That's basically about the same core question all other again:</p>
<ul>
<li>do we explicitely pass context along with the things</li>
</ul>
<p>or</p>
<ul>
<li>do we store context as a field in the thing</li>
</ul>
<p>?</p>



<a name="188108152"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188108152" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188108152">(Feb 13 2020 at 13:59)</a>:</h4>
<p>cc <span class="user-mention" data-user-id="129457">@Florian Diebold</span> in case you have some brilliant idea how to deal with it.</p>



<a name="188110618"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188110618" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188110618">(Feb 13 2020 at 14:29)</a>:</h4>
<p>no brilliant idea, but I feel like if we do generate mirrored APIs for <code>InFile&lt;AstNode&gt;</code>s (and maybe add further context and give it a better name than <code>InFile</code>), we can get an acceptable API</p>



<a name="188110669"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188110669" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188110669">(Feb 13 2020 at 14:29)</a>:</h4>
<blockquote>
<p>maybe add further context </p>
</blockquote>
<p><code>Ctx&lt;T&gt;</code> ? :)</p>



<a name="188110770"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188110770" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188110770">(Feb 13 2020 at 14:30)</a>:</h4>
<p>Note that generating API would require to duplicate AST traits, like <code>TypeParamsOwner</code> as well</p>



<a name="188111053"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188111053" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188111053">(Feb 13 2020 at 14:33)</a>:</h4>
<p>yeah, and duplicating hand-written extensions :(</p>



<a name="188111128"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188111128" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188111128">(Feb 13 2020 at 14:34)</a>:</h4>
<p>maybe we could invert it to <code>SyntaxNode&lt;Context&gt;</code> <span aria-label="thinking" class="emoji emoji-1f914" role="img" title="thinking">:thinking:</span></p>



<a name="188111159"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188111159" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188111159">(Feb 13 2020 at 14:34)</a>:</h4>
<p>so the current syntax nodes would be <code>SyntaxNode&lt;()&gt;</code></p>



<a name="188111175"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188111175" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188111175">(Feb 13 2020 at 14:34)</a>:</h4>
<p>Yeah, that's another option</p>



<a name="188111210"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188111210" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188111210">(Feb 13 2020 at 14:35)</a>:</h4>
<p>I'd even say we can make it on-generic, by using <code>SyntaxNode&lt;u64&gt;</code>, because everybody should use indexes anyway</p>



<a name="188111326"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188111326" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188111326">(Feb 13 2020 at 14:36)</a>:</h4>
<p>And I think that's how most compiles work: sytnax generally remmebers a file it originated from, which is usually good enough for identity</p>



<a name="188111350"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188111350" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188111350">(Feb 13 2020 at 14:36)</a>:</h4>
<p>I think Swift's libsyntax is an expcetion: they don't store the original file, or any other bits of context</p>



<a name="188111358"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188111358" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188111358">(Feb 13 2020 at 14:37)</a>:</h4>
<p>I feel like if we define <code>type SyntaxNode = SyntaxNode&lt;()&gt;</code> the parameter probably wouldn't be annoying</p>



<a name="188111402"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188111402" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188111402">(Feb 13 2020 at 14:37)</a>:</h4>
<p>And i really, really love that design, abstractly. But I don't see we how that would square with API we want...</p>



<a name="188111479"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188111479" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188111479">(Feb 13 2020 at 14:38)</a>:</h4>
<p>so what kind of API does swift have?</p>



<a name="188111537"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188111537" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188111537">(Feb 13 2020 at 14:39)</a>:</h4>
<p>I belive that haven't move semantic analysis over libsyntax yet, so they don't have an API which requires identity at all</p>



<a name="188111557"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188111557" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188111557">(Feb 13 2020 at 14:39)</a>:</h4>
<p>ah <span aria-label="grimacing" class="emoji emoji-1f62c" role="img" title="grimacing">:grimacing:</span></p>



<a name="188111641"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188111641" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188111641">(Feb 13 2020 at 14:40)</a>:</h4>
<p>I think they do have strong pointer identity of trees though, so, in theory, they can use pointer-keyed hash maps</p>



<a name="188112237"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188112237" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188112237">(Feb 13 2020 at 14:47)</a>:</h4>
<p>It's also interesting how we hit this problem because of macros. </p>
<p>Before, you were generally working with syntax from a single file, so there was no need for fine-grained tweaking of the context.</p>
<p>Now, you can hold several trees simulatenously, which originate from different macros, and kind-a need to pair a tree with ctx...</p>



<a name="188112592"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188112592" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188112592">(Feb 13 2020 at 14:50)</a>:</h4>
<p>btw,</p>
<blockquote>
<p>It does not actually yield a true global identity, because the same file can be included twice into a module tree of a crate (Note how this makes syntax&lt;-&gt;semantics not a bijection, which is painful to deal with).</p>
</blockquote>
<p>should that maybe lead to different <code>HirFileId</code>s?</p>



<a name="188112746"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188112746" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188112746">(Feb 13 2020 at 14:51)</a>:</h4>
<p>if we have multiple copies of a whole crate in the crate graph because of e.g. configurations, does that lead to different <code>HirFileId</code>s?</p>



<a name="188112881"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188112881" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188112881">(Feb 13 2020 at 14:52)</a>:</h4>
<p>Yeah, I think we need to somehow fix it, and to make HirFileId unambgious. Last time I've looked into it I've hit a chicken and egg problem though</p>



<a name="188112941"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188112941" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188112941">(Feb 13 2020 at 14:53)</a>:</h4>
<p>Basically, what we need is to include a <code>ModuleId</code> into <code>HIrFileId</code>. However, we can't get a <code>ModuleId</code> before we parse it's file into <code>raw</code> items. </p>
<p>And the query to get <code>raw</code> items needs a file id!</p>



<a name="188117430"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188117430" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188117430">(Feb 13 2020 at 15:35)</a>:</h4>
<p>Looked at Roslyn, I think their magic is relying on trees identity: <a href="http://sourceroslyn.io/#Microsoft.CodeAnalysis.CSharp/Compilation/SyntaxTreeSemanticModel.cs,1710" target="_blank" title="http://sourceroslyn.io/#Microsoft.CodeAnalysis.CSharp/Compilation/SyntaxTreeSemanticModel.cs,1710">http://sourceroslyn.io/#Microsoft.CodeAnalysis.CSharp/Compilation/SyntaxTreeSemanticModel.cs,1710</a></p>



<a name="188117798"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188117798" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188117798">(Feb 13 2020 at 15:38)</a>:</h4>
<p>And that's actually is interesting, because, unlike <code>SyntaxNode&lt;Context&gt;</code>, the context is meaningless. Ie, does this mean that we don't even need an index, and just <code>SyntaxNode&lt;impl Eq&gt;</code>?</p>



<a name="188118520"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188118520" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188118520">(Feb 13 2020 at 15:45)</a>:</h4>
<p>Ok, I think I am onto something!</p>



<a name="188124603"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188124603" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188124603">(Feb 13 2020 at 16:42)</a>:</h4>
<p>So, this is the proposal:</p>
<ul>
<li>We add an <code>u32</code> field, <code>tree_identity</code>, to <code>rowan::SyntaxNode</code>. By default it is assigned to <code>0</code>, but there's an option to provide your own value when constructing a tree.  All nodes within a tree share a <code>tree_identity</code></li>
<li>Rowan takes this <code>tree_identity</code> into account when implementing <code>Eq</code> &amp; <code>Hash</code>, with the rule that if you parse the three twice from the same string and the same identity, the correspoinding nodes will be equal, and nodes with different identities will always be distinct (this last part is what is not satisfied by rowan today). This gives us essentially "pointer identity", except that it's fine to reparse trees</li>
<li>We add <code>rowan::SyntaxNode::identity_key</code>, which returns an opaque <code>Copy</code> key which you can, eg, store in a hash map without holding the whole tree</li>
<li>In <code>hir</code>, we assign tree identities to macro files and file-root modules. I think this requires the use of salsa interning, but this is an implementation detail. We only need to make sure that id does not change if the module did not change, we won't use <code>lookup_</code> query at all. </li>
<li>the API to get types of things will be based on trees with identities. <ul>
<li>you start with asking for a syntax tree for a particular file. A tree with <em>some</em> identity is returned (this is inheritnly ambigious due to aliasing modules)</li>
<li>in the tree, you find an ast::Expr</li>
<li>you find an ast::FnDef which contains the expression</li>
<li>you ask for hir::Function for this ast::FnDef. This works, roughly, by listing all functions and finding the one which originates from the same <code>tree_identity</code> and position. </li>
<li>we typecheck the function, getting a map from <code>SyntaxNode</code>s to types, whcih includes all macro-expanded files</li>
<li>we look the result up in the map</li>
</ul>
</li>
</ul>



<a name="188127916"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188127916" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> std::Veetaha <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188127916">(Feb 13 2020 at 17:15)</a>:</h4>
<p>I remember you saying that green node doesn't have an identity and is easily interned, but red one has through the parent pointer. I guess these properties are preserved with your proposal, aren't they? And if Syntax Node already has an identity, making it global seems reasonable</p>



<a name="188128205"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188128205" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188128205">(Feb 13 2020 at 17:18)</a>:</h4>
<p>Exactly! Green node still is identity less. SyntaxNode gets a real identity (currently, it has identity within the file, and comparison of nodes across files is just ill-defined and might return <code>true</code>)</p>



<a name="188128375"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188128375" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> std::Veetaha <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188128375">(Feb 13 2020 at 17:20)</a>:</h4>
<p>Heh, looks like ub when you put it like that)</p>



<a name="188128418"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188128418" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188128418">(Feb 13 2020 at 17:20)</a>:</h4>
<p>yeah, that might actually work out <span aria-label="thinking" class="emoji emoji-1f914" role="img" title="thinking">:thinking:</span></p>



<a name="188128605"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188128605" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> std::Veetaha <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188128605">(Feb 13 2020 at 17:22)</a>:</h4>
<p>But, are there sensible caveats?</p>



<a name="188128752"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188128752" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> std::Veetaha <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188128752">(Feb 13 2020 at 17:24)</a>:</h4>
<p>Maybe it is ridiculous, but what is an estimate of increased memory usage? I remember you being concerned about usize vs u32 for TextUnit</p>



<a name="188129058"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188129058" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188129058">(Feb 13 2020 at 17:27)</a>:</h4>
<p>We don't increase the size of GreenNodes, the size of SyntaxNodes does not matter that much as there are few of them, and otherwise we add roughly one u32 + interning metadata per file/macro</p>



<a name="188462417"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188462417" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188462417">(Feb 18 2020 at 15:53)</a>:</h4>
<p>Ok, I am experiemnting with it right now, and I have a problem: I need a thing, which is exactly like SourceBinder and SourceAnalyzer, but different from those, and I need a name for it <span aria-label="laughter tears" class="emoji emoji-1f602" role="img" title="laughter tears">:laughter_tears:</span></p>



<a name="188462635"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188462635" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188462635">(Feb 18 2020 at 15:56)</a>:</h4>
<p>shouldn't we be able to get rid of <code>SourceAnalyzer</code> with this <span aria-label="thinking" class="emoji emoji-1f914" role="img" title="thinking">:thinking:</span> </p>
<p>also, what does the new thing do?</p>



<a name="188462815"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188462815" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188462815">(Feb 18 2020 at 15:58)</a>:</h4>
<p>The same, but without <code>InFile&lt;T&gt;</code></p>



<a name="188462849"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188462849" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188462849">(Feb 18 2020 at 15:58)</a>:</h4>
<p>well, it doesn't do anything yet, because it doesn't exist, but I think we should be able to cut own <strong>a lot</strong> of <code>InFile</code>s with it</p>



<a name="188463115"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188463115" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188463115">(Feb 18 2020 at 16:01)</a>:</h4>
<p><a href="/user_uploads/4715/n0kc6ze_-A6-h9HyR1OheK_p/pasted_image.png" target="_blank" title="pasted_image.png">pasted image</a></p>
<div class="message_inline_image"><a href="/user_uploads/4715/n0kc6ze_-A6-h9HyR1OheK_p/pasted_image.png" target="_blank" title="pasted image"><img src="/user_uploads/4715/n0kc6ze_-A6-h9HyR1OheK_p/pasted_image.png"></a></div>



<a name="188463173"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188463173" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188463173">(Feb 18 2020 at 16:02)</a>:</h4>
<p>The above is what we have now, the bellow is what I want</p>



<a name="188463275"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188463275" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188463275">(Feb 18 2020 at 16:03)</a>:</h4>
<p>why not <code>token.descend_into_macros(&amp;source_binder)</code> / <code>token.ancestors_with_macros</code>?</p>



<a name="188463356"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188463356" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188463356">(Feb 18 2020 at 16:04)</a>:</h4>
<p>That would require an extension trait</p>



<a name="188463457"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188463457" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188463457">(Feb 18 2020 at 16:05)</a>:</h4>
<p>That's actually exactly how C# API looks like I think: <a href="https://github.com/dotnet/roslyn/wiki/Getting-Started-C%23-Semantic-Analysis" target="_blank" title="https://github.com/dotnet/roslyn/wiki/Getting-Started-C%23-Semantic-Analysis">https://github.com/dotnet/roslyn/wiki/Getting-Started-C%23-Semantic-Analysis</a></p>



<a name="188463487"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188463487" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188463487">(Feb 18 2020 at 16:05)</a>:</h4>
<p>And yes, I hope this new thing subsumes bothe SourceBinder and SourceAnalyzer</p>



<a name="188463637"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188463637" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188463637">(Feb 18 2020 at 16:06)</a>:</h4>
<p>Also, as a minor point, I think we <em>should</em> use caches like in <code>SourceBinder</code>, but we should hide them behind <code>RefCell</code>, so that we dont' need <code>mut</code> al over the place</p>



<a name="188463674"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188463674" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188463674">(Feb 18 2020 at 16:07)</a>:</h4>
<p>how about calling it <code>RustAnalyzer</code> <span aria-label="big smile" class="emoji emoji-1f604" role="img" title="big smile">:big_smile:</span></p>



<a name="188463687"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188463687" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188463687">(Feb 18 2020 at 16:07)</a>:</h4>
<p>more seriously, maybe just <code>Analyzer</code></p>



<a name="188463766"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188463766" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188463766">(Feb 18 2020 at 16:08)</a>:</h4>
<p>Note that we already have <code>Analysis</code>. I acutally think that <code>SemanticModel</code> / <code>Semantics</code> might be a good name.</p>



<a name="188463774"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188463774" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188463774">(Feb 18 2020 at 16:08)</a>:</h4>
<p>Because that's what it is -- semantics ascribed to syntax</p>



<a name="188463951"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188463951" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188463951">(Feb 18 2020 at 16:10)</a>:</h4>
<p>I'm not a fan of <code>SemanticModel</code> because it doesn't seem to contain the actual model</p>



<a name="188464001"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188464001" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188464001">(Feb 18 2020 at 16:11)</a>:</h4>
<p><code>SemanticApi</code>?</p>



<a name="188464788"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188464788" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Emil Lauridsen <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188464788">(Feb 18 2020 at 16:18)</a>:</h4>
<p><span class="user-mention silent" data-user-id="133169">matklad</span> <a href="#narrow/stream/185405-t-compiler.2Fwg-rls-2.2E0/topic/Design.20question.3A.20identity.20in.20syntax.20trees/near/188464001" title="#narrow/stream/185405-t-compiler.2Fwg-rls-2.2E0/topic/Design.20question.3A.20identity.20in.20syntax.20trees/near/188464001">said</a>:</p>
<blockquote>
<p><code>SemanticApi</code>?</p>
</blockquote>
<p>That doesn't seem too unreasonable</p>



<a name="188464812"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188464812" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188464812">(Feb 18 2020 at 16:19)</a>:</h4>
<p>I like that more... though I think <code>Semantics</code> might also be fine</p>



<a name="188464922"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188464922" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188464922">(Feb 18 2020 at 16:20)</a>:</h4>
<p>does it actually contain any context, apart from the source binder cache thing?</p>



<a name="188464962"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188464962" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188464962">(Feb 18 2020 at 16:20)</a>:</h4>
<p>Yeah, i guess the main Q is whether this API flies at all. It might, and if it does, it should simplify <strong>everything</strong> a lot (also, I am scared by amount of refactorig this will require to complete)</p>



<a name="188465005"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188465005" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188465005">(Feb 18 2020 at 16:21)</a>:</h4>
<blockquote>
<p>does it actually contain any context, apart from the source binder cache thing?</p>
</blockquote>
<p>Yeah, I imagine it would contain a ton of hash maps keyed by SyntaxNodes</p>



<a name="188465057"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188465057" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Emil Lauridsen <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188465057">(Feb 18 2020 at 16:21)</a>:</h4>
<p>I'm a big fan of designing APIs by writing the usage code first, and then iterating from there, so it seems like a good starting point</p>



<a name="188465058"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188465058" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188465058">(Feb 18 2020 at 16:21)</a>:</h4>
<p>At least, it'll have something like <code>HashMap&lt;TreeId, HirFileId&gt;</code></p>



<a name="188465086"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188465086" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188465086">(Feb 18 2020 at 16:21)</a>:</h4>
<p>hmm I thought that would be in the db?</p>



<a name="188465145"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188465145" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188465145">(Feb 18 2020 at 16:22)</a>:</h4>
<p>or the db contains the other direction, and this needs to reverse it?</p>



<a name="188465216"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188465216" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188465216">(Feb 18 2020 at 16:23)</a>:</h4>
<p>I guess I'll just wait how it actually looks ;)</p>



<a name="188465230"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188465230" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188465230">(Feb 18 2020 at 16:23)</a>:</h4>
<p>In general, I'd expect the other direction</p>



<a name="188465319"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188465319" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188465319">(Feb 18 2020 at 16:23)</a>:</h4>
<p>well, acutally, I don't really know myself yet :)</p>



<a name="188465408"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188465408" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188465408">(Feb 18 2020 at 16:24)</a>:</h4>
<p>But rowan branch with ids is <a href="https://github.com/rust-analyzer/rowan/tree/identity" target="_blank" title="https://github.com/rust-analyzer/rowan/tree/identity">https://github.com/rust-analyzer/rowan/tree/identity</a></p>



<a name="188465846"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188465846" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188465846">(Feb 18 2020 at 16:28)</a>:</h4>
<blockquote>
<p>well, acutally, I don't really know myself yet :)</p>
</blockquote>
<p>So, I think the general idea is rougthly what we already do with <code>SourceBinder</code>. </p>
<p>We <strong>store</strong> things like</p>
<div class="codehilite"><pre><span></span><span class="k">struct</span> <span class="nc">Parent</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">   </span><span class="n">children</span>: <span class="nc">FxHashMap</span><span class="o">&lt;</span><span class="n">Name</span><span class="p">,</span><span class="w"> </span><span class="n">Child</span><span class="o">&gt;</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
</pre></div>


<p>and, in general, we want to do look up by <code>Child</code>. We do this recursively -- we lookup parent, than <em>inver</em>  and cache (in semantics) the children map and lookup the node by id it it</p>



<a name="188465933"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188465933" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188465933">(Feb 18 2020 at 16:29)</a>:</h4>
<p>so it's still just a cache, right?</p>



<a name="188465959"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188465959" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188465959">(Feb 18 2020 at 16:29)</a>:</h4>
<p>right</p>



<a name="188466047"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188466047" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188466047">(Feb 18 2020 at 16:30)</a>:</h4>
<p>basically, the three lines starting from here <a href="http://sourceroslyn.io/#Microsoft.CodeAnalysis.CSharp/Compilation/SyntaxTreeSemanticModel.cs,1708" target="_blank" title="http://sourceroslyn.io/#Microsoft.CodeAnalysis.CSharp/Compilation/SyntaxTreeSemanticModel.cs,1708">sourceroslyn.io/#Microsoft.CodeAnalysis.CSharp/Compilation/SyntaxTreeSemanticModel.cs,1708</a>, is the solution to all our API problems</p>



<a name="188466059"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188466059" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188466059">(Feb 18 2020 at 16:30)</a>:</h4>
<p>hopefully :D</p>



<a name="188466103"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188466103" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188466103">(Feb 18 2020 at 16:30)</a>:</h4>
<p>ah, nope, the core is actually the outer for</p>



<a name="188466115"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188466115" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188466115">(Feb 18 2020 at 16:30)</a>:</h4>
<p><a href="http://sourceroslyn.io/#Microsoft.CodeAnalysis.CSharp/Compilation/SyntaxTreeSemanticModel.cs,1695" target="_blank" title="http://sourceroslyn.io/#Microsoft.CodeAnalysis.CSharp/Compilation/SyntaxTreeSemanticModel.cs,1695">http://sourceroslyn.io/#Microsoft.CodeAnalysis.CSharp/Compilation/SyntaxTreeSemanticModel.cs,1695</a></p>



<a name="188472715"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188472715" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188472715">(Feb 18 2020 at 17:37)</a>:</h4>
<p>Did a minimal thing here: <a href="https://github.com/rust-analyzer/rust-analyzer/pull/3222" target="_blank" title="https://github.com/rust-analyzer/rust-analyzer/pull/3222">https://github.com/rust-analyzer/rust-analyzer/pull/3222</a></p>



<a name="188472904"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188472904" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188472904">(Feb 18 2020 at 17:39)</a>:</h4>
<p>The funniest thing is that I think we don't need a strong identity for this to work. I need to think through this tomorrow, but it looks like the fact that we store syntax nodes in the cache solves the potential problem when we get two different trees due to LRU.</p>



<a name="188473038"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188473038" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188473038">(Feb 18 2020 at 17:40)</a>:</h4>
<p>And yes, semancits creates source binder which creates source analyzer =/</p>



<a name="188480625"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188480625" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jeremy Kolb <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188480625">(Feb 18 2020 at 19:03)</a>:</h4>
<p>Would strong identity still be worth having?</p>



<a name="188481772"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188481772" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188481772">(Feb 18 2020 at 19:16)</a>:</h4>
<p>well, this approach only works if we only obtain syntax nodes through the <code>Semantics</code> thing, right?</p>



<a name="188486749"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188486749" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jeremy Kolb <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188486749">(Feb 18 2020 at 20:12)</a>:</h4>
<p>Right. I was thinking it could be useful for someone else</p>



<a name="188494902"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/188494902" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#188494902">(Feb 18 2020 at 21:48)</a>:</h4>
<blockquote>
<p>well, this approach only works if we only obtain syntax nodes through the Semantics thing, right?</p>
</blockquote>
<p>I think this is true for any identity based approach. If all you have is an identity, the only way to get something out of it is to look it up in a hashmap which was created by an entity that returned you this thing with identity</p>



<a name="189020298"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/189020298" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#189020298">(Feb 25 2020 at 13:46)</a>:</h4>
<p>Lol, turns out rowan has a bug, in that it tries to use pointer equality, but unfortunately there's one more level of indiretcion, and i was comparing pointers to pointers :)</p>



<a name="189021464"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/189021464" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> std::Veetaha <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#189021464">(Feb 25 2020 at 14:01)</a>:</h4>
<p>You should add a test for that...</p>



<a name="189021532"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/189021532" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Laurențiu <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#189021532">(Feb 25 2020 at 14:02)</a>:</h4>
<p>Was it wrong or only slower?</p>



<a name="189021578"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/189021578" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#189021578">(Feb 25 2020 at 14:02)</a>:</h4>
<p>wrong</p>



<a name="189021795"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/189021795" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> std::Veetaha <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#189021795">(Feb 25 2020 at 14:05)</a>:</h4>
<p>But what changed? It still compares <code>ptr() == ptr()</code>...</p>



<a name="189022056"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/189022056" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#189022056">(Feb 25 2020 at 14:08)</a>:</h4>
<p>it's now a <code>*const NodeData</code>, rather than <code>*const *const NodeData</code></p>



<a name="189022875"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Design%20question%3A%20identity%20in%20syntax%20trees/near/189022875" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> std::Veetaha <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Design.20question.3A.20identity.20in.20syntax.20trees.html#189022875">(Feb 25 2020 at 14:19)</a>:</h4>
<p>We can compare <code>*const NodeData</code> pointerwise because they are interned right?</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>